package com.test.daily.leetcode.y2022.m05.day0518.v07;

/**
 * @descriptions: Solution
 * @author: Tom
 * @date: 2022/5/18 下午 04:34
 * @version: 1.0
 */
public class Solution {
    public static void radixSorted(int[] arr) {
        int digit = getBits(arr);
        int radix = 10;
        int[] help = new int[arr.length];
        for (int d = 1; d <= digit; d++) {
            int[] counts = new int[radix];
            for (int i = 0; i < arr.length; i++) {
                int j = getDigit(arr[i], d);
                counts[j]++;
            }
            for (int j = 1; j < radix; j++) {
                counts[j] += counts[j - 1];
            }
            for(int i = arr.length - 1;i >= 0; i-- ){
                int j = getDigit(arr[i],d);
                help[counts[j]-1] = arr[i];
                --counts[j];
            }
        }
        for (int i = 0; i < arr.length; i++) {
            arr[i] = help[i];
        }
    }

    public static int getBits(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        int res = 0;
        while (max != 0) {
            res++;
            max /= 10;
        }
        return res;
    }

    public static int getDigit(int value, int count) {
        int ans = (value / (int) Math.pow(10, count - 1)) % 10;
        return ans;
    }
}
